import math
from collections import defaultdict

class CraftingHelperCore:
    """合成助手核心类"""
    def __init__(self, item_list):
        self.item_list = item_list
    
    def solve(self, targetList, ignoreList):
        """计算合成路线，包括剩余材料"""
        # 初始化数据结构
        indegree = defaultdict(int)
        needs_count = defaultdict(float)  # 物品需求量
        production_count = defaultdict(float)  # 生产次数
        excess_count = defaultdict(float)  # 剩余材料计数器
        
        # 初始化目标物品需求
        for item_dict in targetList:
            item = item_dict["item"]
            count = item_dict["count"]
            needs_count[item] = count
            indegree[item] = 0  # 初始入度为0
            
        # BFS构建依赖图
        queue = list(needs_count.keys())
        index = 0
        
        while index < len(queue):
            item = queue[index]
            index += 1
            
            # 跳过不在合成表中或忽略的物品
            if item not in self.item_list or item in ignoreList:
                continue
                
            # 处理当前物品的所有材料
            for material, material_per_craft in self.item_list[item]["materialList"]:
                # 增加材料的入度
                indegree[material] += 1
                
                # 如果材料尚未在队列中，添加它
                if material not in queue:
                    queue.append(material)
        
        # 拓扑排序 - 使用队列而不是栈
        processing_queue = [item for item in queue if indegree[item] == 0]
        
        # 处理队列
        while processing_queue:
            product = processing_queue.pop(0)
            
            # 跳过不在合成表中或忽略的物品
            if product not in self.item_list or product in ignoreList:
                continue
                
            # 计算当前物品的生产次数
            output_per_craft = self.item_list[product]["count"]
            required_count = needs_count[product]
            
            # 计算需要生产多少次
            craft_count = math.ceil(required_count / output_per_craft)
            production_count[product] = craft_count
            
            # 计算剩余材料（实际生产量 - 需求量）
            excess = craft_count * output_per_craft - required_count
            if excess > 0:
                excess_count[product] += excess
            
            # 更新材料需求
            for material, material_per_craft in self.item_list[product]["materialList"]:
                # 增加材料需求
                needs_count[material] += craft_count * material_per_craft
                
                # 减少材料的入度
                indegree[material] -= 1
                
                # 如果材料的入度为0，添加到处理队列
                if indegree[material] == 0:
                    processing_queue.append(material)
        
        # 基础材料
        basic_material = []
        for item in needs_count:
            if item not in self.item_list or item in ignoreList:
                # 只添加有需求的基础材料
                if needs_count[item] > 0:
                    basic_material.append({
                        "item": item,
                        "count": needs_count[item]
                    })
        
        # 合成路线
        made_route = []
        # 按照生产顺序添加合成路线
        for product in production_count:
            if product in self.item_list and product not in ignoreList:
                table = self.item_list[product]
                craft_count = production_count[product]
                product_count = craft_count * table["count"]
                material_list = []
                
                # 收集材料列表
                for material, material_per_craft in table["materialList"]:
                    material_list.append((material, material_per_craft * craft_count))
                
                made_route.append({
                    "product": product,
                    "productCount": product_count,
                    "machine": table["machine"],
                    "materialList": material_list
                })
        
        # 多余物品（剩余材料）
        extra_item = []
        for product, excess in excess_count.items():
            if excess > 0:
                extra_item.append({
                    "item": product,
                    "count": excess
                })
        
        # 添加最终产品的剩余材料
        for item_dict in targetList:
            final_item = item_dict["item"]
            target_count = item_dict["count"]
            
            # 计算最终产品的实际生产量
            actual_production = production_count.get(final_item, 0) * self.item_list.get(final_item, {"count": 1})["count"]
            
            # 计算剩余量
            final_excess = actual_production - target_count
            if final_excess > 0:
                # 检查是否已有此物品的剩余记录
                existing = next((item for item in extra_item if item["item"] == final_item), None)
                if existing:
                    existing["count"] += final_excess
                else:
                    extra_item.append({
                        "item": final_item,
                        "count": final_excess
                    })
        
        return {
            "basicMaterial": basic_material,
            "madeRoute": made_route,
            "extraItem": extra_item
        }
